package datastruct

import "sync"

// 链表队列，先进先出
type LinkQueue struct {
	Root *QueueNode // 链表起点
	Size int        // 队列的元素数量
	lock sync.Mutex // 为了并发安全使用的锁
}

// 链表节点
type QueueNode struct {
	Next  *QueueNode
	Value string
}

// 入队
func (queue *LinkQueue) Add(v string) {
	queue.lock.Lock()
	defer queue.lock.Unlock()

	// 如果栈顶为空，那么增加节点
	if queue.Root == nil {
		queue.Root = new(QueueNode)
		queue.Root.Value = v
	} else {
		// 否则新元素插入链表的末尾
		// 新节点
		newNode := new(QueueNode)
		newNode.Value = v

		// 一直遍历到链表尾部
		nowNode := queue.Root
		for nowNode.Next != nil {
			nowNode = nowNode.Next
		}

		// 新节点放在链表尾部
		nowNode.Next = newNode
	}

	// 队中元素数量+1
	queue.Size = queue.Size + 1
}

// 出队
func (queue *LinkQueue) Remove() string {
	queue.lock.Lock()
	defer queue.lock.Unlock()

	// 队中元素已空
	if queue.Size == 0 {
		panic("empty")
	}

	// 顶部元素要出队
	topNode := queue.Root
	v := topNode.Value

	// 将顶部元素的后继链接链上
	queue.Root = topNode.Next

	// 队中元素数量-1
	queue.Size = queue.Size - 1

	return v
}
